import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

class LeafNode extends Node {
    List<Integer> key;
    List<Data> data;
    LeafNode next;
    int dataNum;

    LeafNode(int n, InternalNode father) {
        key = new LinkedList<>();
        data = new LinkedList<>();
        this.father = father;
        dataNum = n;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("叶节点").append(count).append(" ");
        sb.append("  键值[");
        for (int k : key) {
            sb.append(k).append(" ");
        }
        sb.append("]  数值[");
        for (Data s : data) {
            sb.append(s.data).append(" ");
        }
        sb.append("]  ");
        if (next != null)
            sb.append("后继").append(next.count).append("  ");
        else
            sb.append("无后继   ");
        if (father != null)
            sb.append("父节点").append(father.count).append("\n");
        else
            sb.append("无父节点");
        return sb.toString();
    }

    public Node delete(int key) {
        Node result = null;
        Iterator<Data> it = this.data.iterator();
        Iterator<Integer> keyIt = this.key.iterator();
        boolean delete = false;
        while (it.hasNext()) {
            Data d = it.next();
            keyIt.next();
            if (d.key == key) {
                it.remove();
                keyIt.remove();
                delete = true;
                break;
            }
        }
        if (!delete) {
            System.out.println("无效的键");
            return result;
        }

        if (isNearUnder()) {
            InternalNode f = this.father;
            int index = this.getIndex();
            if (index > 0 && !f.son.get(index - 1).isNearUnder()) {
                LeafNode leftsib = (LeafNode) f.son.get(index - 1);
                int modifiedKey = leftsib.key.remove(leftsib.key.size() - 1);
                Data modifiedData = leftsib.data.remove(leftsib.data.size() - 1);
                this.key.add(0, modifiedKey);
                this.data.add(0, modifiedData);
                f.modifyIndex(modifiedKey, index - 1);
            } else if (index < f.son.size() - 1 && !f.son.get(index + 1).isNearUnder()) {
                LeafNode rightsib = (LeafNode) f.son.get(index + 1);
                int modifiedKey = rightsib.key.remove(0);
                Data modifiedData = rightsib.data.remove(0);
                this.key.add(modifiedKey);
                this.data.add(modifiedData);
                f.modifyIndex(rightsib.data.get(0).key, index);
            } else if (index > 0) {
                LeafNode leftsib = (LeafNode) f.son.get(index - 1);
                leftsib.merge(this);
                result = father.delete(index - 1);
            } else if (index < f.son.size() - 1) {
                this.merge(this.next);
                result = father.delete(index);
            }
        }
        return result;
    }

    public NodeKey insert(int key, String data) {
        int loc = this.key.size();
        for (int i = 0; i < this.key.size(); i++) {
            if (key < this.key.get(i)) {
                loc = i;
                break;
            }
        }
        this.key.add(loc, key);
        this.data.add(loc, new Data(key, data));

        if (this.isFull()) {
            int median = (this.dataNum + 1) / 2;
            LeafNode newNode = new LeafNode(this.dataNum, this.father);
            int full_size = this.key.size();
            for (int i = median; i < full_size; i++) {
                newNode.key.add(this.key.get(median));
                this.key.remove(median);
                newNode.data.add(this.data.get(median));
                this.data.remove(median);
            }
            newNode.next = this.next;
            this.next = newNode;
            return new NodeKey(newNode, newNode.key.get(0));
        } else {
            return null;
        }
    }

    public boolean isFull() {
        return this.data.size() == this.dataNum;
    }

    @Override
    public boolean isNearUnder() {
        return (this.data.size() - 1) < (this.dataNum) * 0.5;
    }

    public Data getSon(int i) {
        return this.data.get(i);
    }

    public InternalNode getFather() {
        return father;
    }

    public int getKey(int i) {
        return this.key.get(i);
    }

    @Override
    void merge(Node n) {
        assert n instanceof LeafNode;
        LeafNode l = (LeafNode) n;
        this.next = l.next;
        Iterator<Integer> keyIt = l.key.iterator();
        Iterator<Data> dataIt = l.data.iterator();
        while (keyIt.hasNext()) {
            this.key.add(keyIt.next());
            this.data.add(dataIt.next());
        }
    }
}
